package dp;

public class UniquePath {

	public static void main(String[] args) {
		int[][] obstacleGrid = {{0,0,0,0,0},
				                {0,0,0,0,0},
				                {0,0,0,1,0},
				                {0,0,0,0,0},
				                {0,0,0,0,0},
				                {0,0,0,0,0},
				                {0,0,0,0,2},};
//		System.out.println(uniquePaths(100, 100));
//		System.out.println(uniquePaths2(obstacleGrid));
		System.out.println(pathCount(obstacleGrid,7,5));
	}

	//dp[i][j]表示从0到坐标i，j的方法数
	//dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
	public static long uniquePaths(int m, int n) {
		long[][] result = new long[m + 1][n + 1];
		for (int i = 0; i < result.length; i++) {
			result[i][1] = 1;
		}
		for (int i = 0; i < result[0].length; i++) {
			result[1][i] = 1;
		}
		for (int i = 2; i < result.length; i++) {
			for (int j = 2; j < result[0].length; j++) {
				result[i][j] = result[i - 1][j] + result[i][j - 1];
			}
		}
		return result[m][n];
	}
	
	//运行时间：89ms
	//占用内存：1952k  可能有时是long型数组的原因
	//如果添加障碍
	//if(obstacleGrid[i][j] == 1) 那么肯定就是0了
	//如果不为1，那么就和上面的一样
	public static long uniquePaths2(int[][] obstacleGrid) {
		if(obstacleGrid == null || obstacleGrid.length <= 0){
			return  -1;
		}
		int m = obstacleGrid.length;
		int n = obstacleGrid[0].length;
		long[][] result = new long[m + 1][n + 1];
		for (int i = 1; i < result.length; i++) {
			if (obstacleGrid[i - 1][0] == 0) {
				result[i][1] = 1;
			}else {
				//注意这里break的原因是一旦左边的无法到达，那么右边的肯定无法到达
				break;
			}
		}
		for (int i = 1; i < result[0].length; i++) {
			if (obstacleGrid[0][i - 1] == 0) {
				result[1][i] = 1;
			}else {
				//同上，一旦上面的无法到达，那么下面的也无法到达
				break;
			}
		}
		for (int i = 2; i < result.length; i++) {
			for (int j = 2; j < result[0].length; j++) {
				if (obstacleGrid[i - 1][j - 1] == 1) {
					result[i][j] = 0;
				} else {
					result[i][j] = result[i - 1][j] + result[i][j - 1];
				}
			}
		}
		for (long[] ls : result) {
			for (long l : ls) {
				System.out.print(l + " ");
			}
			System.out.println(" ------");
		}
		return result[m][n];
	}
	
	//现在有一个城市销售经理，需要从公司出发，去拜访市内的商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，
	//他只能在左右中选择一个方向，在上下中选择一个方向，现在问他有多少种方案到达商家地址。
	
	//给定一个地图map及它的长宽n和m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区
	//意思应该是如果选择了往左走，那么之后就只能一直往左走，同理，上下也是一样的
	
	//这道题首先还得知道起点和终点，而且选择往哪个方向走
	public static int pathCount(int[][] map, int n, int m){
		//首先找到起点和终点的位置
		int xStart = 0, yStart = 0;
		boolean find1 = false, find2 = false;
		int xEnd = 0, yEnd = 0;
		//注意是中断整个循环
		label:
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if(map[i][j] == 1){
					xStart = i;
					yStart = j;
					find1 = true;
				}
				if(map[i][j] == 2){
					xEnd = i;
					yEnd = j;
					find2 = true;
				}
				if(find1 & find2){
					break label;
				}
			}
		}
		//注意：从A到B的路径等于从B到A的路径，于是可以统一成向下走，然后分为左下以及右下
		System.out.println("xs" + xStart + "xe" + xEnd +"ys" + yStart + "ye" + yEnd);
		if(xStart == xEnd || yStart == yEnd){
			return 1;  //由于 保证一定有路径
		}
		int[][] result ;
		int rightDir = 1; 
		//只能选左
		if(yEnd - yStart < 0){
			rightDir = -1;
		}
		// 就可以交换两者的信息了
		if (xStart > xEnd) {// x1,y1用于保存行下标的较小者
			// 首先用yEnd保存yStart的值，此时两个yStart的值相亦或为0，0与yEnd 亦或为yEnd，故最终yStart为yEnd
			yStart = yStart ^ yEnd ^ (yEnd = yStart);
			xStart = xStart ^ xEnd ^ (xEnd = xStart);
		}
		int xDiff = Math.abs(xEnd - xStart);
		int yDiff = Math.abs(yEnd - yStart);
		result = new int[n][m];
		result[xStart][yStart] = 1;
		for (int i = xStart + 1; i <= xEnd ; i++) {
			if (map[i][yStart] == 0) {
				result[i][yStart] = 1;
			}else if(map[i][yStart] == -1){
				//注意这里break的原因是一旦左(右)边的无法到达，那么右(左)边的肯定无法到达
				break;
			}
		}
		for (int j = yStart + rightDir ; j != yEnd + rightDir; j += rightDir) {
			if (map[xStart][j] == 0) {
				result[xStart][j] = 1;
			}else if(map[xStart][j] == -1){
				//同上，一旦上面的无法到达，那么下面的也无法到达
				break;
			}
		}
		for (int i = xStart; i <= xEnd; i++) {
			for (int j = yStart; j != yEnd + rightDir; j += rightDir) {
				System.out.print("beford : i : " + i + " j: "+ j + "  "+ result[i][j]);
			}
			System.out.println();
		}
		//注意这里不能用<= 来判断是否结束了，因为不知道是往左还是往右了
		for (int j = yStart + rightDir; j != yEnd + rightDir; j += rightDir) {
			System.out.println("j: " + j +"i: ");
			for (int i = xStart + 1; i <= xEnd; i++) {
				System.out.println("i: " + i +"j: " + j);
				if (map[i][j] == -1) {
					result[i][j] = 0;
				} else {
					result[i][j] = result[i - 1][j] + result[i][j - rightDir];
				}
				System.out.println("res" + result[i][j]);
			}
		}
		return result[xEnd][yEnd];
	}
}
